package org.laizili.solution.leetcode;

import org.laizili.structure.tree.bitree.TreeNode;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/most-frequent-subtree-sum/">508. 出现次数最多的子树元素和</a>
 *
 * <p>tags:
 * 二叉树; 后序遍历;
 */
public class Problem508 {
    private static class Solution {

        public int[] findFrequentTreeSum(TreeNode root) {
            Map<Integer, Integer> numCount = new HashMap<>();
            sum(root, numCount);
            List<Integer> ans = new ArrayList<>();
            sum(root, numCount);
            int max = numCount.values().stream().max(Integer::compareTo).get();
            for (var entry : numCount.entrySet()) {
                if (entry.getValue() == max) {
                    ans.add(entry.getKey());
                }
            }
            return ans.stream().mapToInt(Integer::intValue).toArray();
        }

        private int sum(TreeNode root, Map<Integer, Integer> numCount) {
            if (root != null) {
                int left = sum(root.left, numCount);
                int right = sum(root.right, numCount);
                int total = left + right + root.val;
                int totalCnt = numCount.getOrDefault(total, 0) + 1;
                numCount.put(total, totalCnt);
                return total;
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode node5 = new TreeNode(0);
        System.out.println(Arrays.toString(solution.findFrequentTreeSum(node5)));
    }
}
